graph nonisomorphism problem

Definition

• Input: pair of graphs, $(G,H)$
• Output: whether or not $G \ncong H$

Notes

• $\mathtt{GNI} \in$ IP (hence there is an IPS for GNI)
• $\mathtt{GNI} \in$ coNP

References

1. https://people.csail.mit.edu/ronitt/COURSE/S12/handouts/lec6.pdf